翻訳と辞書 Words near each other ・ Extensible Forms Description Language ・ Extensible Host Controller Interface ・ Extensible Metadata Platform ・ Extensible ML ・ Extensible MPEG-4 Textual Format ・ Extended cycle combined hormonal contraceptive ・ Extended Data Services ・ Extended day program ・ Extended discrete element method ・ Extended Display Identification Data ・ Extended Duration Orbiter ・ Extended ELM2 domain ・ Extended enterprise ・ Extended Enterprise Modeling Language ・ Extended essay ・ Extended Euclidean algorithm ・ Extended Evolutionary Synthesis ・ Extended family ・ Extended file attributes ・ Extended file system ・ Extended finite element method ・ Extended finite-state machine ・ Extended Groth Strip ・ Extended Hückel method ・ Extended Industry Standard Architecture ・ Extended interaction oscillator ・ Extended interframe space ・ Extended irreversible thermodynamics ・ Extended Kalman filter ・ Extended Log Format Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Extended Euclidean algorithm ： ウィキペディア英語版 Extended Euclidean algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, which computes, besides the greatest common divisor of integers ''a'' and ''b'', the coefficients of Bézout's identity, that is integers ''x'' and ''y'' such that : $ax\; +\; by\; =\; \backslash gcd(a,\; b).$ It allows one to compute also, with almost no extra cost, the quotients of ''a'' and ''b'' by their greatest common divisor. Extended Euclidean algorithm also refers to a very similar algorithm for computing the polynomial greatest common divisor and the coefficients of Bézout's identity of two univariate polynomials. The extended Euclidean algorithm is particularly useful when ''a'' and ''b'' are coprime, since ''x'' is the modular multiplicative inverse of ''a'' modulo ''b'', and ''y'' is the modular multiplicative inverse of ''b'' modulo ''a''. Similarly, the polynomial extended Euclidean algorithm allows one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non prime order. It follows that both extended Euclidean algorithms are widely used in cryptography. In particular, the computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method. == Description== The standard Euclidean algorithm proceeds by a succession of Euclidean divisions whose quotients are not used, only the ''remainders'' are kept. For the extended algorithm, the successive quotients are used. More precisely, the standard Euclidean algorithm with ''a'' and ''b'' as input, consists of computing a sequence $q\_1,\backslash ldots,\; q\_k$ of quotients and a sequence $r\_0,\backslash ldots,\; r\_$ of remainders such that :$$ \begin r_0=a\\ r_1=b\\ \ldots\\ r_=r_-q_i r_i \quad \text \quad 0\le r_ < |r_i|\\ \ldots \end It is the main property of Euclidean division that the inequalities on the right define uniquely $r\_$ from $r\_$ and $r\_.$ The computation stops when one reaches a remainder $r\_$ which is zero; the greatest common divisor is then the last non zero remainder $r\_.$ The extended Euclidean algorithm proceeds similarly, but adds two other sequences, as follows :$$ \begin r_0=a\qquad r_1=b\\ s_0=1\qquad s_1=0\\ t_0=0\qquad t_1=1\\ \ldots\\ r_=r_-q_i r_i \quad \text \quad 0\le r_ < |r_i|\qquad \text q_i \text\\ s_=s_-q_i s_i\\ t_=t_-q_i t_i\\ \ldots \end The computation also stops when $r\_=0$ and gives *$r\_$ is the greatest common divisor of the input $a=r\_$ and $b=r\_.$ * The Bézout coefficients are $s\_$ and $t\_,$ that is $\backslash gcd(a,b)=r\_=as\_k+bt\_k$ * The quotients of ''a'' and ''b'' by their greatest common divisor are given by $s\_=\backslash pm\backslash frac$ and $t\_=\backslash pm\backslash frac$ Moreover, if ''a'' and ''b'' are both positive, we have : This means that the pair of Bézout's coefficients provided by the extended Euclidean algorithm is one of the two minimal pairs of Bézout coefficients. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Extended Euclidean algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.